home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / minix / up1510b.tgz / up1510b / src / commands / ttt.c < prev    next >
C/C++ Source or Header  |  1990-07-19  |  6KB  |  281 lines
  1. /* tic tac toe (noughts and crosses)        Author: Warren Toomey */
  2.  
  3. /* Copyright (C) 1988 Warren Toomey.
  4.   You may use, copy, modify, or give this away provided you
  5.   1. make the source available with every copy.
  6.   2. include this notice.
  7.   3. don't use this for military purposes.
  8.   (but you can take credit for improvements, etc.)
  9. */
  10.  
  11. /* Compile with cc -o tic tic.c -lcurses -ltermcap */
  12.  
  13. #define CURSES
  14. #ifdef CURSES
  15. /*  #include <curses.h>         Used by the real curses  */
  16. #endif
  17.  
  18. #ifndef CURSES
  19. #define printw printf
  20. #endif
  21.  
  22.  
  23. typedef struct {
  24.   int value;            /* The move returned by the    */
  25.   int path;            /* alphabeta consists of a value */
  26. } MOVE;                /* and an actual move (path)   */
  27.  
  28.  
  29.  /* Static evaluator. Returns 100 if we have 3 in a row -100 if they have 3
  30.   * in a row
  31.   * 
  32.   * Board is array of 9 ints, where 0=empty square 1=our move 4= their move
  33.   * 
  34.   * and board is indices    0 1 2 3 4 5 6 7 8 */
  35.  
  36.  
  37. int stateval(board, whosemove)
  38. int board[];
  39.  
  40. {
  41.   static int row[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8},    /* Indices of 3in-a-rows */
  42.             {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
  43.             {0, 4, 8}, {2, 4, 6}};
  44.  
  45.   int temp;            /* Temp row results */
  46.   int i, j;            /* Loop counters */
  47.   int side;            /* Depth multiplier */
  48.   int win, lose;
  49.  
  50.   if (whosemove == 1) {
  51.     win = 100;
  52.     lose = -100;
  53.     side = 1;
  54.   } else {
  55.     /* Multiply by -1 if */
  56.     win = -100;
  57.     lose = 100;
  58.     side = -1;
  59.   }                /* not out move */
  60.   for (i = 0; i < 8; i++) {    /* For every 3-in-a-row */
  61.     temp = 0;
  62.     for (j = 0; j < 3; j++)    /* Add up the board values */
  63.         temp += board[row[i][j]];
  64.  
  65.     if (temp == 3) return(win);    /* We've got 3 in a row */
  66.     if (temp == 12) return (lose);    /* They've got 3 in a row */
  67.   }
  68.   return(0);            /* Finally return sum */
  69. }
  70.  
  71.  
  72. MOVE alphabeta(board, whosemove, alpha, beta)    /* Alphabeta: takes a board, */
  73. int board[];            /* whose move, alpha & beta cutoffs, */
  74. int whosemove;            /* and returns a move to make and */
  75. int alpha;            /* the value that the move has */
  76. int beta;
  77. {
  78.   MOVE result, successor;
  79.   int best_score, i, best_path, mademove;
  80.  
  81.   result.value = stateval(board, whosemove);    /* Work out the board's */
  82.   /* Static value */
  83.   if ((result.value == 100) ||    /* If a win or loss already */
  84.       (result.value == -100))
  85.     return(result);    /* return the result */
  86.  
  87.   best_score = beta;        /* Ok, set worst score */
  88.   mademove = 0;            /* to the beta cutoff */
  89.   for (i = 0; i < 9; i++) {
  90.     if (board[i] == 0) {    /* For all valid moves */
  91.         mademove = 1;
  92.         board[i] = whosemove;    /* make the move on board */
  93.         successor = alphabeta(board, 5 - whosemove, -best_score - 1, -alpha - 1);
  94.         /* Get value of the move */
  95.         board[i] = 0;    /* Take move back */
  96.         if (-successor.value > best_score) {    /* If a better score */
  97.             best_score = -successor.value;    /* update our score */
  98.             best_path = i;    /* and move */
  99.             if (best_score > alpha)
  100.                 break;    /* If we've beaten alpha */
  101.         }        /* return immediately */
  102.     }
  103.   }
  104.   if (mademove) {
  105.     result.value = best_score;    /* Finally return best score */
  106.     result.path = best_path;/* and best move */
  107.   }
  108.   return(result);        /* If no move, return static result */
  109. }
  110.  
  111.  
  112. draw(board)            /* Draw the board */
  113. int board[];
  114. {
  115.   int i, j, row;
  116.   static char out[] = " X  O";    /* Lookup table for character */
  117.  
  118.   row = 6;
  119. #ifdef CURSES
  120.   move(row, 0);
  121. #endif
  122.   for (j = 0; j < 9; j += 3) {
  123.     printw(" %d | %d | %d     ", j, j + 1, j + 2);
  124.     for (i = 0; i < 3; i++) {
  125.         printw("%c ", out[board[j + i]]);
  126.         if (i < 2) printw("| ");
  127.     }
  128.     if (j < 4) {
  129. #ifdef CURSES
  130.         move(++row, 0);
  131. #else
  132.         printw("\n");
  133. #endif
  134.         printw("---+---+---   ---+---+---");
  135.     }
  136. #ifdef CURSES
  137.     move(++row, 0);
  138. #else
  139.     printw("\n");
  140. #endif
  141.   }
  142. #ifdef CURSES
  143.   refresh();
  144. #else
  145.   printw("\n");
  146. #endif
  147. }
  148.  
  149.  
  150. getmove(board)            /* Get a player's move */
  151. int board[];
  152. {
  153.   int Move;
  154.  
  155.   do {
  156.     do {
  157. #ifdef CURSES
  158.         move(9, 40);
  159.         printw("Your move: ");    /* Prompt for move */
  160.         refresh();
  161. #else
  162.         printw("Your move: ");    /* Prompt for move */
  163. #endif
  164.     }
  165.     while (scanf("%d", &Move) != 1);    /* Input the move */
  166.   }
  167.   while (board[Move]);
  168.   board[Move] = 4;        /* If legal, add to board */
  169.   draw(board);            /* Draw the board */
  170. }
  171.  
  172.  
  173. int endofgame(board)        /* Determine end of the game */
  174. int board[];
  175. {
  176.   int eval;
  177.   int count;
  178.  
  179.   eval = stateval(board, 1);
  180. #ifdef CURSES
  181.   move(20, 25);
  182. #endif
  183.   if (eval == 100) {
  184.     printw("I have beaten you.\n");
  185.     return(1);
  186.   }
  187.   if (eval == -100) {
  188.     printw("Bus error (core dumped)\n");
  189.     return(1);
  190.   }
  191.   count = 0;
  192.   for (eval = 0; eval < 9; eval++)
  193.     if (board[eval] != 0) count++;
  194.   if (count == 9) {
  195.     printw("A draw!\n");
  196.     return(1);
  197.   }
  198. #ifdef CURSES
  199.   refresh();
  200. #endif
  201.   return(0);
  202. }
  203.  
  204.  
  205. int randommove()
  206. {                /* Make an initial random move */
  207.   long time();            /* based on current time */
  208.   int i;
  209.  
  210.   i = abs((int) time((long *) 0));
  211.   return(i % 9);
  212. }
  213.  
  214.  
  215. main()
  216. {                /* The actual game */
  217.   int i, board[9];
  218.   char ch;
  219.   MOVE ourmove;
  220.  
  221.   for (i = 0; i < 9; i++) board[i] = 0;    /* Initialise the board */
  222. #ifdef CURSES
  223.   initscr();
  224.   clear();
  225.   refresh();
  226. #endif
  227.   printw("                           TIC TAC TOE   \n\n");
  228.   printw("                        Your moves are 'O'\n");
  229.   printw("                         My moves are 'X'\n\n");
  230. #ifdef CURSES
  231.   move(5, 0);
  232.   printw("Do you wish to move first: ");
  233.   refresh();
  234.   while (scanf("%c", &ch) != 1);
  235.   move(5, 0);
  236.   printw("                         .......");    /* Kludge to get rid */
  237.   refresh();
  238.   move(5, 0);
  239.   printw("                                ");    /* of input letter */
  240.   refresh();
  241. #else
  242.   do
  243.     printw("Do you wish to move first: ");
  244.   while (scanf("%c", &ch) != 1);
  245. #endif
  246.   if ((ch != 'y') && (ch != 'Y')) {
  247.     i = randommove();    /* If we move first */
  248.     board[i] = 1;        /* make it random */
  249. #ifdef CURSES
  250.     move(7, 42);
  251.     printw("My move: %d\n", i);
  252.     refresh();
  253. #else
  254.     printw("My move: %d\n", i);
  255. #endif
  256.   }
  257.   draw(board);
  258.   getmove(board);
  259.  
  260.   while (1) {
  261.     ourmove = alphabeta(board, 1, 99, -99);    /* Get a move for us;
  262.                          * return wins */
  263.     /* Immediately & ignore losses */
  264.     board[ourmove.path] = 1;/* and make it */
  265. #ifdef CURSES
  266.     move(7, 42);
  267.     printw("My move: %d\n", ourmove.path);
  268.     refresh();
  269. #else
  270.     printw("My move: %d\n", ourmove.path);
  271. #endif
  272.     draw(board);
  273.     if (endofgame(board)) break;    /* If end of game, exit */
  274.     getmove(board);        /* Get opponent's move */
  275.     if (endofgame(board)) break;    /* If end of game, exit */
  276.   }
  277. #ifdef CURSES
  278.   endwin();
  279. #endif
  280. }
  281.